package com.cqs.leetcode.sort;

import com.cqs.leetcode.ListNode;

/**
 * @author lixiaowen
 * @create 2019-12-23
 */
public class InsertionSortList147 {

    public ListNode insertionSortList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode cur = head.next, next = null, target = head, targetNext;
        head.next = null;//避免构成环
        while (cur != null) {
            next = cur.next;
            //利用上一次遍历的结果 避免每次都从head开始遍历
            target = target.val <= cur.val ? target : head;
            if (cur.val < target.val) {
                //说明cur的值是当前最小，需要更新head
                cur.next = head;
                head = cur;
            }else {
                while (target.next != null && target.next.val < cur.val) {
                    target = target.next;
                }
                //交换cur插入target之前，target.next之后
                targetNext = target.next;
                target.next = cur;
                cur.next = targetNext;
            }
            cur = next;
        }
        return head;
    }

    public static void main(String[] args) {
        InsertionSortList147 insert = new InsertionSortList147();
        //15->14->10->23->7->3->14->14->16->27->14->8->7->22->3
        int[] arr = new int[]{15,14,10,23,7,3,14,14,16,27,14,8,7,22,3};
//         arr = new int[]{14,15};
        ListNode head = ListNode.randomLink(100);
//        head = ListNode.build(arr);
        System.out.println(head);
        head = insert.insertionSortList(head);
        System.out.println(head);

    }
}